% Ejercicio "Tres gramáticas"
\subsection*{\fbox{\theejercicio} - Tres gram\'aticas}

Construir las tablas de an\'alisis LL(1) para los lenguajes generados por las siguientes gram\'aticas. En caso de que la gram\'atica propuesta no sea LL(1), hallar una gram\'atica equivalente y construir para ella la tabla. Todos los lenguajes est\'an definidos sobre el alfabeto verb${ a,b,c,d }$.

\begin{center}
\begin{tabular}{|l|l|l|} \hline
                                      &                                             &                                             \\
{\em A} $\rightarrow$ {\bf a}{\em BC} & {\em A} $\rightarrow$ {\bf a}{\em A}{\bf c} & {\em A} $\rightarrow$ {\em A}{\bf a}{\em B} \\
{\em A} $\rightarrow$ {\em BC}        & {\em A} $\rightarrow$ {\em AB}              & {\em A} $\rightarrow$ {\bf a}{\em B}        \\
{\em B} $\rightarrow$ {\bf b}{\em B}  & {\em A} $\rightarrow$ {\em B}               & {\em A} $\rightarrow$ {\em B}{\bf a}        \\
{\em B} $\rightarrow$ $\varepsilon$   & {\em B} $\rightarrow$ {\bf b}               & {\em A} $\rightarrow$ {\em AB}{\bf a}       \\
{\em C} $\rightarrow$ {\bf c}{\em C}  & {\em B} $\rightarrow$ {\em B}{\bf d}{\em B} & {\em B} $\rightarrow$ {\em B}{\bf bcd}      \\
{\em C} $\rightarrow$ $\varepsilon$   &                                             & {\em B} $\rightarrow$ {\bf bcd}             \\
                                      &                                             &                                             \\ \hline
\end{tabular}
\end{center}

% Solución del ejercicio
\subsubsection*{SOLUCI\'ON}

Gram\'atica 1)

La gram\'atica es LL(1), y la tabla de an\'alisis es la siguiente:

\begin{center}
\begin{tabular}{|l|ccccc|} \hline
        & {\bf a}       & {\bf b}        & {\bf c}        & {\bf d} & {\bf \$}      \\ \hline
{\em A} & {\bf}{\em BC} & {\em BC}       & {\em BC}       &         & {\em BC}      \\
{\em B} &               & {\bf b}{\em B} & $\varepsilon$  &         & $\varepsilon$ \\
{\em C} &               &                & {\bf c}{\em C} &         & $\varepsilon$ \\ \hline
\end{tabular}
\end{center}

Gram\'atica 2)

La gram\'atica no es LL(1). La siguiente gram\'atica genera el mismo lenguaje y s\'{\i} lo es:

\begin{center}
\begin{tabular}{|lcl|} \hline
         &               &                               \\
{\em A}  & $\rightarrow$ & {\bf a}{\em A}{\bf c}{\em A'} \\
{\em A}  & $\rightarrow$ & {\em BA'}                     \\
{\em A'} & $\rightarrow$ & {\em BA'}                     \\
{\em A'} & $\rightarrow$ & $\varepsilon$                 \\
{\em B}  & $\rightarrow$ & {\bf b}{\em B'}               \\
{\em B'} & $\rightarrow$ & {\bf db}{\em B'}              \\
{\em B'} & $\rightarrow$ & $\varepsilon$                 \\
         &               &                               \\ \hline
\end{tabular}
\end{center}

Cuya tabla de an\'alisis LL(1) es:

\begin{center}
\begin{tabular}{|l|ccccc|} \hline
         & {\bf a}                       & {\bf b}         & {\bf c}       & {\bf d}          & {\bf \$}      \\ \hline
{\em A}  & {\bf a}{\em A}{\bf c}{\em A'} & {\em BA'}       & $\varepsilon$ &                  &               \\
{\em A'} &                               & {\em BA'}       &               &                  &               \\
{\em B}  &                               & {\bf b}{\em B'} &               &                  &               \\
{\em B'} &                               &                 & $\varepsilon$ & {\bf db}{\em B'} & $\varepsilon$ \\ \hline
\end{tabular}
\end{center}

Gram\'atica 3)

La gram\'atica no es LL(1). En este caso resulta complicado obtener una gram\'atica equivalente que cumpla las condiciones LL(1), ya que las transformaciones heur\'{\i}ísticas de eliminaci\'on de recursividad izquierda y de factorizaci\'on no dan resultados satisfactorios. Sin embargo, si se analiza el lenguaje generado se llega a la conclusi\'on que se trata de un lenguaje regular, cuya expresi\'on regular es la siguiente:

\begin{center}
{\bf (abb$^*$ $|$ bb$^*$a)  (abb$^*$ $|$ bb$^*$a)$^*$}
\end{center}

en donde {\bf b} representa a la cadena \verb@"bcd"@.

\par A partir de esta expresi\'on es trivial construir el aut\'omata finito que reconoce esta expresi\'on regular:

% Imagen del auotómata finito determinista
\begin{center}
\includegraphics[0cm,0cm][12.25cm,5.08cm]{./capitulo3/ejercicios/figuras/automata1.jpg}
\end{center}


Y a partir de \'este, mediante unas sencillas transformaciones se obtiene el aut\'omata finito determinista:

% Imagen del auotómata finito determinista transformado
\begin{center}
\includegraphics[0cm,0cm][7.78cm,6.09cm]{./capitulo3/ejercicios/figuras/automata2.jpg}
\end{center}

A partir de este aut\'omata finito determinista se construye directamente la gram\'atica LL(1):

\begin{center}
\begin{tabular}{|lcl|} \hline
        &               &                  \\
{\em A} & $\rightarrow$ & {\bf a}{\em B}   \\
{\em A} & $\rightarrow$ & {\bf bcd}{\em E} \\
{\em B} & $\rightarrow$ & {\bf bcd}{\em C} \\
{\em C} & $\rightarrow$ & {\bf a}{\em B}   \\
{\em C} & $\rightarrow$ & {\bf bcd}{\em D} \\
{\em C} & $\rightarrow$ & $\varepsilon$    \\
{\em D} & $\rightarrow$ & {\bf a}{\em C}   \\
{\em D} & $\rightarrow$ & {\bf bcd}{\em D} \\
{\em D} & $\rightarrow$ & $\varepsilon$    \\
{\em E} & $\rightarrow$ & {\bf a}{\em F}   \\
{\em E} & $\rightarrow$ & {\bf bcd}{\em E} \\
{\em F} & $\rightarrow$ & {\bf a}{\em B}   \\
{\em F} & $\rightarrow$ & {\bf bcd}{\em E} \\
{\em F} & $\rightarrow$ & $\varepsilon$    \\
        &               &                  \\ \hline
\end{tabular}
\end{center}

cuya tabla de an\'alisis LL(1) es:

\begin{center}
\begin{tabular}{|l|ccccc|} \hline
        & {\bf a}        & {\bf b}          & {\bf c} & {\bf d} & {\bf \$}      \\ \hline
{\em A} & {\em AB}       & {\bf bcd}{\em E} &         &         &               \\ \hline
{\em B} &                & {\bf bcd}{\em C} &         &         &               \\ \hline
{\em C} & {\bf a}{\em B} & {\bf bcd}{\em C} &         &         & $\varepsilon$ \\ \hline
{\em D} & {\bf a}{\em C} & {\bf bcd}{\em D} &         &         & $\varepsilon$ \\ \hline
{\em E} & {\bf a}{\em F} & {\bf bcd}{\em E} &         &         &               \\ \hline
{\em F} & {\bf a}{\em B} & {\bf bcd}{\em E} &         &         & $\varepsilon$ \\ \hline
\end{tabular}
\end{center}